package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.RandomNode;

/**
 * 复杂链表的复制
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9835.%20%E5%A4%8D%E6%9D%82%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%8D%E5%88%B6/README
 */
public class P35 {
    public static void main(String[] args) {

    }


    class Solution {
        public RandomNode copyRandomList(RandomNode head) {
            if (head == null) {
                return null;
            }
            // 复制链表节点
            // A->B->C变成A->A1->B->B1->C->C1
            RandomNode cur = head;
            while (cur != null) {
                RandomNode next = cur.next;
                cur.next = new RandomNode(cur.val);
                cur.next.next = next;
                cur = next;
            }
            // 复制随机节点
            cur = head;
            while (cur != null) {
                RandomNode curNew = cur.next;
                curNew.random = cur.random == null ? null : cur.random.next;
                cur = cur.next;
            }
            // 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
            RandomNode headNew = head.next;
            cur = head;
            RandomNode curNew = head.next;
            while (cur !=null) {
                cur.next = cur.next.next;
                cur = cur.next;
                curNew.next = curNew.next.next;
                curNew = curNew.next;
            }
            return headNew;

        }
    }

}
